package leetcode.editor.cn;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Administrator
 * @description 99. 恢复二叉搜索树
 * @date 2023/4/2 0002
 */
public class Solution99 {
    int max = Integer.MIN_VALUE, diffNum, index;

    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new LinkedList<TreeNode>();
        // 遍历树
        traversalTree(root, list);
        TreeNode x = null;
        TreeNode y = null;
        //扫面遍历的结果，找出可能存在错误交换的节点x和y
        for(int i=0;i<list.size()-1;++i) {
            if(list.get(i).val>list.get(i+1).val) {
                y = list.get(i+1);
                if(x==null) {
                    x = list.get(i);
                }
            }
        }
        //如果x和y不为空，则交换这两个节点值，恢复二叉搜索树
        if(x!=null && y!=null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    private void traversalTree(TreeNode root, List<TreeNode> list) {
        if (root == null){
            return;
        }
        traversalTree(root.left, list);
        list.add(root);
        traversalTree(root.right, list);
    }


}
